package leetcode.动态规划和贪心;

import java.util.List;
/*
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

相邻的意思是，当前的 index 是 i 的话
下一个需要寻找的就是 i 和 i+1

贪心可以解决此问题，当然动态规划也行
 */
public class Test120三角形最小路径和 {

    public int minimumTotal(List<List<Integer>> triangle) {
        // 一个记录和的变量
        int sum = 0;
        // 遍历最大的 List，里面再遍历小的 List，用 startIndex 标记小的 list 应该从哪里开始
        int startIndex = 0;
        for (int i = 0; i < triangle.size(); i++) {
            // 每一个小的 List 的长度等于当前这个小 List 在大 List 里面的位置 +1
            if (triangle.get(i).size() == 1) {
                sum += triangle.get(i).get(0);
                continue;
            }

            if (startIndex + 1 < triangle.get(i).size() &&
                    triangle.get(i).get(startIndex) <= triangle.get(i).get(startIndex + 1)) {
                sum += triangle.get(i).get(startIndex);
            } else {
                sum += triangle.get(i).get(startIndex + 1);
                startIndex++;
            }

        }

        return sum;
    }


    public int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        // 自底向上，记录每一层的最小值即可
        int[] dp = new int[triangle.size() + 1];

        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> curTr = triangle.get(i);
            for (int j = 0; j < curTr.size(); j++) {
                // 这里的 dp[j] 使用的时候默认是上一层的，赋值之后变成当前层
                // min 函数先找到上一层的最小值，然后加上本层的得到结果
                // 为什么是加上本层的第 j 个元素呢：这样才叫相邻（反过来看，本层的j和下一层的j以及j+1）
                dp[j] = Math.min(dp[j], dp[j + 1]) + curTr.get(j);
            }
        }
        return dp[0];
    }
}
